package com.jjlin.chapter_2;
import java.util.*;

public class CD156{
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static Node createBinaryTree(int[][] nums){
        HashMap<Integer, Node> map = new HashMap<>();
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            map.putIfAbsent(nums[i][0], new Node(nums[i][0]));
            if (nums[i][1] != 0) {
                map.putIfAbsent(nums[i][1], new Node(nums[i][1]));
                map.get(nums[i][0]).left = map.get(nums[i][1]);
            }
            if (nums[i][2] != 0) {
                map.putIfAbsent(nums[i][2], new Node(nums[i][2]));
                map.get(nums[i][0]).right = map.get(nums[i][2]);
            }
        }
        return map.get(nums[0][0]);
    }

    //解法1：利用队列存储二叉树的中序遍历，然后逐个形成双向链表，时间复杂度为O(N)，空间复杂度为O(N)
    public static Node convert(Node head){
        if(head == null)
            return head;
        Queue<Node> queue = inorderUnRecur(head);
        head = queue.poll();
        Node pre = head;
        pre.left = null;
        Node cur = null;
        while(!queue.isEmpty()){
            cur = queue.poll();
            pre.right = cur;//将right改为双向链表中next指针
            cur.left = pre;//将left改为双向链表中pre指针
            pre = cur;
        }
        pre.right = null;
        return head;
    }

    //将中序遍历的结果存储在队列中并返回
    public static Queue<Node> inorderUnRecur(Node head){
        Stack<Node> stack = new Stack<>();
        Queue<Node> queue = new LinkedList();
        Node cur = head;
        while(!stack.isEmpty() || cur != null){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                queue.offer(cur);//存储节点到队列中
                cur = cur.right;
            }
        }
        return queue;
    }

    //解法2：利用递归(书本上解法)，时间复杂度为O(N)，空间复杂度为O(h),h为二叉树高度
    public static Node convert1(Node head){
        if(head == null)
            return null;
        Node last = process(head);
        head = last.right;
        last.right = null;
        return head;
    }

    public static Node process(Node head){
        if(head == null)
            return head;
        Node leftE = process(head.left);
        Node rightE = process(head.right);
        Node leftS = leftE != null ? leftE.right : null;
        Node rightS = rightE != null ? rightE.right : null;
        if(leftE != null && rightE != null){
            leftE.right = head;
            head.left = leftE;
            head.right = rightS;
            rightS.left = head;
            rightE.right = leftS;
            return rightE;
        }else if(leftE != null){
            leftE.right = head;
            head.left = leftE;
            head.right = leftS;
            return head;
        }else if(rightE != null){
            head.right = rightS;
            rightS.left = head;
            rightE.right = head;
            return rightE;
        }else{
            head.right = head;
            return head;
        }
    }

    //打印改造后的双向链表
    public static void printDoubleNodeList(Node head){
        StringBuilder res = new StringBuilder();
        while (head != null) {
            res.append(head.val).append(" ");
            head = head.right;
        }
        System.out.println(res.substring(0, res.length() - 1));
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        Node head = createBinaryTree(nums);
        head = convert(head);
        printDoubleNodeList(head);
    }
}
